package com.kevin.learn.leetcode;

import com.alibaba.fastjson.JSON;
import com.kevin.learn.domain.ListNode;

public class 递归反转链表 {

    public static void main(String[] args) {
        ListNode num1 = new ListNode(1);
        ListNode num2 = new ListNode(2);
        ListNode num3 = new ListNode(3);
        ListNode num4 = new ListNode(4);
        num3.setNext(num4);
        num2.setNext(num3);
        num1.setNext(num2);

        //        ListNode reverse = reverse(num1);

        //        ListNode reverse = reverseN(num1, 2);

        ListNode reverse = reverseBetween(num1, 2, 3);
        System.out.println(JSON.toJSON(reverse));
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head.next == null)
            return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    public static ListNode successor = null; // 后驱节点

    // 反转以 head 为起点的 n 个节点，返回新的头结点
    public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }

    // 反转链表的一部分
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // base case
        if (m == 1) {
            return reverseN(head, n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
}
